package com.study.algorithm.ordinaryArray;

public class FirstMissingPositive {
    public int firstMissingPositive(int[] nums) {
      /*  思路：对于一个长度为 n 的数组，缺失的最小正整数一定在 [1, n+1] 之间。
        如果 1 到 n 都出现过，那么缺失的是 n+1。
        否则，缺失的数字一定在 [1, n] 之间。*/

        int n = nums.length;
        // 第一步：将所有非正整数和大于n的数替换为n+1
        for (int i = 0; i < n; i++) {
            if (nums[i] <0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }
        // 第二步：标记存在的数字（将对应索引处的数变为负数）
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]); // 取绝对值，因为可能已经被标记为负数
            if (num <= n) { // 只处理1到n的数字
                int index = num - 1;
                if (nums[index] > 0) { // 避免重复标记
                    nums[index] = -nums[index];
                }
            }
        }
        // 第三步：找到第一个正数的索引，对应的i+1就是缺失的数字
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        // 如果所有1到n的数字都存在，则缺失n+1
        return n + 1;
    }

    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        System.out.println(new FirstMissingPositive().firstMissingPositive(nums));
    }
}